﻿/*
    在一个数组 nums 中除一个数字只出现一次之外，
    其他数字都出现了三次。
    请找出那个只出现一次的数字。
 */

using System;
using System.Collections.Generic;
using System.Linq;

namespace JZ_56_shu_zu_zhong_shu_zi_chu_xian_de_ci_shu_ii_lcof
{
    class Program
    {
        static void Main (string[] args)
        {
            int[] nums = new int[] { 9, 4, 7, 9, 7, 9, 7 };
            Console.WriteLine (SingleNumber1(nums));
        }

        public static int SingleNumber (int[] nums)
        {
            int ones = 0, twos = 0;
            for (int i = 0;i < nums.Length;i++)
            {
                Console.WriteLine ($"{ones} ^ {nums[i]} = {ones ^ nums[i]} & {~twos} = {ones ^ nums[i] & ~twos}");
                ones = ones ^ nums[i] & ~twos;
                Console.WriteLine ($"{twos} ^ {nums[i]} = {twos ^ nums[i]} & {~ones} = {twos ^ nums[i] & ~ones}");
                twos = twos ^ nums[i] & ~ones;
            }

            return ones;
        }

        public static int SingleNumber1 (int[] nums)
        {
            int[] counts = new int[32];
            for (int i = 0;i < nums.Length;i++)
            {
                for (int j = 0;j < 32;j++)
                {
                    counts[j] += nums[i] & 1;
                    nums[i] = nums[i] >>  1;
                }
            }
            int res = 0, m = 3;
            for (int i = 0;i < 32;i++)
            {
                res = res << 1;
                res |= counts[31 - i] % m;
            }

            return res;
        }

        public static int SingleNumber2 (int[] nums)
        {
            Dictionary<int, int> dic = new Dictionary<int, int> ();
            for (int i = 0;i < nums.Length; i++)
            {
                 dic.Add (nums[i], 0);
                dic[nums[i]]++;
            }
            int num = 0;
            foreach (var item in dic)
            {
                if (item.Value == 1) num = item.Key;
            }
            return num;
        }
    }
}
